#include <stdio.h>
#include <memory.h>

#define XMAX    399
#define YMAX    399
#define NEVER   0xFFFF

typedef struct Point { short x, y; } Point;
Point make_point(short x, short y) 
{
    Point p;
    p.x = x;
    p.y = y;
    return p;
}
static Point queue1[(XMAX+1)*(YMAX+1)];
static Point queue2[(XMAX+1)*(YMAX+1)];

static unsigned short strike[XMAX+1][YMAX+1]; /* time of strike, or NEVER */

/* Returns the minimum number of steps Bessie can get to a meteor-free point,
 * or -1 if this is impossible.
 */
int search()
{
    static const short dx[4] = { -1, 0, 1,  0 };
    static const short dy[4] = {  0, 1, 0, -1 };
    int t = 0;

    Point *input = queue1, *output = queue2, *tmp;
    int num_input = 1;
    input[0] = make_point(0, 0);

    while (num_input > 0)
    {
        int i, num_output = 0;
        for (i = 0; i < num_input; i++)
        {
            Point p = input[i];
            int k;

            if (strike[p.x][p.y] == NEVER)  /* safe */
                return t;
            if (strike[p.x][p.y] <= t)      /* struck or visited */
                continue;
            strike[p.x][p.y] = (short)t;    /* mark as visited */

            for (k = 0; k < 4; k++)
            {
                short x = p.x + dx[k], y = p.y + dy[k];
                if (x >= 0 && x <= XMAX && y >= 0 && y <= YMAX &&
                    strike[x][y] > t + 1)
                    output[num_output++] = make_point(x, y);
            }
        }

        /* Prepare for next second. */
        t++; 
        tmp = input;
        input = output;
        output = tmp;
        num_input = num_output;
    }
    return -1;
}

int main()
{
    int num_meteors, i;
    scanf("%d", &num_meteors);
    memset(strike, -1, sizeof(strike)); /* mark as NEVER */
    for (i = 0; i < num_meteors; i++)
    {
        int x, y, t;
        scanf("%d %d %d", &x, &y, &t);
        if (t < strike[x][y])
            strike[x][y] = (short)t;
        if (x > 0 && t < strike[x-1][y])
            strike[x-1][y] = (short)t;
        if (x < XMAX && t < strike[x+1][y])
            strike[x+1][y] = (short)t;
        if (y > 0 && t < strike[x][y-1])
            strike[x][y-1] = (short)t;
        if (y < YMAX && t < strike[x][y+1])
            strike[x][y+1] = (short)t;
    }
    printf("%d\n", search());
    return 0;
}
